// 有序数组中出现次数超过25%的元素
/*给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5*/
int findSpecialInteger(int* arr, int arrSize) {
    int count = 1;
    for (int i = 1; i < arrSize; i++) {
        if (arr[i] != arr[i - 1]) {
            count = 1;
        } else {
            count++;
        }
        if ((float)count / arrSize * 100 > 25) {
            return arr[i];
        }
    }
    return arr[0];
}



//用栈操作构建数组
/*给你一个数组 target 和一个整数 n。每次迭代，需要从  list = { 1 , 2 , 3 ..., n } 中依次读取一个数字。

请使用下述操作来构建目标数组 target ：

"Push"：从 list 中读取一个新元素， 并将其推入数组中。
"Pop"：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。
1 <= target.length <= 100
1 <= n <= 100
1 <= target[i] <= n
target 严格递增
*/
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** buildArray(int* target, int targetSize, int n, int* returnSize) {
    int target_index = 0;
    char** arr = (char**)calloc(2 * n, sizeof(char*));
    int arr_index = 0;
    for (int i = 1; i <= n; i++) {
        if (target[target_index] == i) {
            arr[arr_index] = "Push";
            arr_index++;
            target_index++;
            if (target_index >= targetSize) {
                *returnSize = arr_index;
                return arr;
            }
        } else {
            arr[arr_index] = "Push";
            arr_index++;
            arr[arr_index] = "Pop";
            arr_index++;
        }
    }
    *returnSize = arr_index;
    return arr;
}